package demo.practice.binary_search;

public class O53 {

    //二分查找
    //[0,1,2,3,4,5,6,7,9,10]  缺少了 8
    // 1  mid位置  nums[mid]=mid 则该元素在 mid之后 如果  nums[mid+1]!=mid+1  则缺少的是 mid+1
                // 2   nums[mid]！=mid （nums[8]=9） 如果   nums[mid-1]== nums[mid-1] 则 缺少的是mid
                //

    public static void main(String[] args) {
        O53 o53= new O53();
        o53.missingNumber(new int[]{1,2,3});
    }
    public int missingNumber(int[] nums) {
        if(nums==null || nums.length==0)
            return -1;
        int max=nums.length-1;
        int min=0;

        while (max>=min){
            int mid=min+(max-min)/2;
            if(nums[mid]==mid){
                if(mid+1==nums.length||nums[mid+1]!=mid+1)
                    return mid+1;
                min=mid+1;
            }else{
                if(mid==0||nums[mid-1]== mid-1)
                    return mid;
                max=mid-1;
            }
        }
        return -1;
    }
}
